#include "../include/nfa.h"
using namespace std;

// --- 1) 将正则表达式转为一个一个的token
vector<string> tokenize(const string &infix)
{
    vector<string> tokens;
    for (size_t i = 0; i < infix.size();)
    {
        char c = infix[i];
        // 跳过空白
        if (isspace(c))
        {
            i++;
            continue;
        }
        // 转义序列，如 \., \n, \|\| 等
        if (c == '\\' && i + 1 < infix.size())
        {
            if (i + 2 < infix.size() && infix[i + 2] == '\\')
            {
                tokens.push_back(infix.substr(i, 4));
                i += 4;
            }
            else
            {
                tokens.push_back(infix.substr(i, 2));
                i += 2;
            }
        }
        // 多字符原子: ==, <=, >=, !=, &&, ||
        else if (i + 1 < infix.size())
        {
            string two = infix.substr(i, 2);
            if (two == "==" || two == "<=" || two == ">=" || two == "!=" || two == "&&")
            {
                tokens.push_back(two);
                i += 2;
            }
            else if (c == '[')
            {
                // 字符类
                size_t j = infix.find(']', i);
                if (j == string::npos)
                    throw runtime_error("Unclosed character class");
                tokens.push_back(infix.substr(i, j - i + 1));
                i = j + 1;
            }
            else if (c == '(' || c == ')' || c == '|' || c == '*' || c == '+' || c == '?')
            {
                // 运算符和括号
                tokens.emplace_back(1, c);
                i++;
            }
            else
            {
                // 普通字面量
                tokens.emplace_back(1, c);
                i++;
            }
        }
        else
        {
            // 单字符处理（行尾情况）
            if (c == '(' || c == ')' || c == '|' || c == '*' || c == '+' || c == '?')
            {
                tokens.emplace_back(1, c);
            }
            else if (c == '[')
            {
                size_t j = infix.find(']', i);
                if (j == string::npos)
                    throw runtime_error("Unclosed character class");
                tokens.push_back(infix.substr(i, j - i + 1));
                i = j + 1;
                continue;
            }
            else
            {
                tokens.emplace_back(1, c);
            }
            i++;
        }
    }
    debug("tokens size=%d\n", tokens.size());
    return tokens;
}

// --- 2) 插入显式串联运算符 '.' ---
vector<string> addConcat(const vector<string> &tokens)
{
    vector<string> output;
    auto isOperand = [&](const string &t)
    {
        // 既不是运算符也不是括号
        return !(t == "|" || t == "." || t == "*" || t == "+" || t == "?" || t == "(" || t == ")");
    };
    for (size_t i = 0; i < tokens.size(); ++i)
    {
        const string &t1 = tokens[i];
        output.push_back(t1);
        if (i + 1 < tokens.size())
        {
            const string &t2 = tokens[i + 1];
            if ((isOperand(t1) || t1 == ")" || t1 == "*" || t1 == "+" || t1 == "?") && (isOperand(t2) || t2 == "("))
            {
                output.push_back(".");
            }
        }
    }
    return output;
}

// --- 3) Shunting Yard算法: 中缀转后缀
vector<string> shunt(const string &infix)
{
    auto tokens = tokenize(infix);
    auto seq = addConcat(tokens);

    unordered_map<string, int> prec = {
        {"*", 60}, {"+", 55}, {"?", 50}, {".", 40}, {"|", 20}};

    vector<string> output;
    stack<string> op;
    for (auto &tok : seq)
    {
        if (tok == "(")
        {
            op.push(tok);
        }
        else if (tok == ")")
        {
            while (!op.empty() && op.top() != "(")
            {
                output.push_back(op.top());
                op.pop();
            }
            if (!op.empty())
                op.pop();
        }
        else if (prec.count(tok))
        {
            while (!op.empty() && prec.count(op.top()) && prec[tok] <= prec[op.top()])
            {
                output.push_back(op.top());
                op.pop();
            }
            op.push(tok);
        }
        else
        {
            // 操作数
            output.push_back(tok);
        }
    }
    while (!op.empty())
    {
        output.push_back(op.top());
        op.pop();
    }
    return output;
}
// Thompson构造法，正则表达式构造NFA
NFA *compile(TokenType type, const vector<string> &postfix)
{
    stack<NFA *> nfaStack;

    for (const string &c : postfix)
    {
        if (c == "*")
        {
            NFA *nfa1 = nfaStack.top();
            nfaStack.pop();
            State *initial = new State();
            State *accept = new State();
            initial->edge1 = nfa1->initial;
            initial->edge2 = accept;
            nfa1->accept->edge1 = nfa1->initial;
            nfa1->accept->edge2 = accept;
            nfaStack.push(new NFA(initial, accept));
        }
        else if (c == "+")
        {
            NFA *nfa1 = nfaStack.top();
            nfaStack.pop();
            State *initial = new State();
            State *accept = new State();
            initial->edge1 = nfa1->initial;
            nfa1->accept->edge1 = nfa1->initial;
            nfa1->accept->edge2 = accept;
            nfaStack.push(new NFA(initial, accept));
        }
        else if (c == "?")
        {
            NFA *nfa1 = nfaStack.top();
            nfaStack.pop();
            State *initial = new State();
            State *accept = new State();
            initial->edge1 = nfa1->initial;
            initial->edge2 = accept;
            nfa1->accept->edge1 = accept;
            nfaStack.push(new NFA(initial, accept));
        }
        else if (c == ".")
        {
            NFA *nfa2 = nfaStack.top();
            nfaStack.pop();
            NFA *nfa1 = nfaStack.top();
            nfaStack.pop();
            nfa1->accept->edge1 = nfa2->initial;
            nfaStack.push(new NFA(nfa1->initial, nfa2->accept));
        }
        else if (c == "|")
        {
            NFA *nfa2 = nfaStack.top();
            nfaStack.pop();
            NFA *nfa1 = nfaStack.top();
            nfaStack.pop();
            State *initial = new State();
            State *accept = new State();
            initial->edge1 = nfa1->initial;
            initial->edge2 = nfa2->initial;
            nfa1->accept->edge1 = accept;
            nfa2->accept->edge1 = accept;
            nfaStack.push(new NFA(initial, accept));
        }
        else
        {
            State *accept = new State();
            State *initial = new State();
            initial->label = c;
            initial->edge1 = accept;
            nfaStack.push(new NFA(initial, accept));
        }
    }
    nfaStack.top()->type = type;
    return nfaStack.top();
}
// 将每个正则表达式的NFA合并成一个大NFA
NFA *merge_nfas(std::stack<NFA *> &nfaLists)
{
    if (nfaLists.empty())
    {
        throw runtime_error("nfaLists is empty!");
    }
    if (nfaLists.size() == 1)
    {
        return nfaLists.top();
    }
    while (nfaLists.size() > 1)
    {
        NFA *top1 = nfaLists.top();
        nfaLists.pop();
        NFA *top2 = nfaLists.top();
        nfaLists.pop();
        State *initial = new State();
        State *accept = new State();
        initial->edge1 = top1->initial;
        initial->edge2 = top2->initial;
        top1->accept->edge1 = accept;
        top2->accept->edge1 = accept;
        nfaLists.push(new NFA(initial, accept));
    }
    return nfaLists.top();
}
// NFA确定化：epsilon闭包计算
set<State *> epsilonClosure(set<State *> &states)
{
    set<State *> closure = states;
    queue<State *> q;
    for (auto s : states)
    {
        q.push(s);
    }
    while (!q.empty())
    {
        State *top = q.front();
        q.pop();
        if (top->label == "")
        {
            if (top->edge1 != nullptr)
            {
                q.push(top->edge1);
                closure.insert(top->edge1);
            }
            if (top->edge2 != nullptr)
            {
                q.push(top->edge2);
                closure.insert(top->edge2);
            }
        }
    }
    return closure;
}
////NFA确定化：token弧转换
set<State *> move(set<State *> &states, const string &token)
{
    set<State *> res;
    for (auto &st : states)
    {
        if (st->label == token)
        {
            res.insert(st->edge1 == nullptr ? st->edge2 : st->edge1);
        }
    }
    return res;
}
